package main

// 位图 ?
// 补码 就是按位取反 再加上 1
// 在补码系统中一个 负数保存的形式是对应正数的补码
// 比如 -1 对应的正数是 1 如果是用 4 位表现 0001 其对应的补码是 1110 + 1 = 1111
// 补码系统可以简化减法计算
// 补码系统中，正数的最高位恒为 0，负数的最高位恒为 1 (由此，最高有效位，代表符号，应该是补码系统的特征)

// 这个算法感觉有点类似于 hash

import (
	"bytes"
	"fmt"
)

type IntSet struct {
	words []uint64
}

// 判断某位是不是存在以此 确定在集合中是不是存在相应的用户
func (s *IntSet) Has(x int) bool {
	word, bit := x/64, uint(x%64)
	// word 存在
	// 按位与，由于 1 << bit 除了有效位数都是 0，因此如果指定位没有设置的话，结果就会是0
	return word < len(s.words) && s.words[word]&(1<<bit) != 0
}

// 同样的 word 可以保存多条数据
// 如何能保证值值不会被覆盖 ?
func (s *IntSet) Add(x int) {
	// 每一个 word 指代一个 64位的 word
	// 然后通过 bit 定位到具体是那一位需要被设置
	word, bit := x/64, uint(x%64)
	for word >= len(s.words) {
		s.words = append(s.words, 0)
	}
	// 将 1 移动到应有的位置
	// 这里使用余数 是为了不超过 64
	// 按位或，可以将指定位置1
	s.words[word] |= 1 << bit
}

func (s *IntSet) UnionWith(t *IntSet) {
	for i, tword := range t.words {
		if i < len(s.words) {
			s.words[i] |= tword
		} else {
			s.words = append(s.words, tword)
		}
	}
}

func (s *IntSet) String() string {
	var buf bytes.Buffer
	buf.WriteByte('{')

	// 通过 word, bit 恢复原有信息
	for i, word := range s.words {
		if word == 0 {
			continue
		}
		// 判断每一个 word 中每一位是否存在,
		// 这里面的 j 就是 Add 中的 bit
		for j := 0; j < 64; j++ {
			if word & (1<<uint(j)) != 0 {
				if buf.Len() > len("{") {
					buf.WriteByte('}')
				}
				fmt.Fprintf(&buf, "%d", 64*i+j)
			}
		}
	}

	buf.WriteByte('}')
	return buf.String()
}

// return the number of elements
// 这里会遇到一个问题: 统计位被置 1 的数量
// Hamming weight (汉名重量)?
func (*IntSet) Len() int {
	return 0
}

// remove x from the set
func (*IntSet) Remove() {

}

// remove all elements from the set
// 全部置零就行了，和自己进行一个异或操作便可
// 或者可以直接在
func (*IntSet) Clear() {

}

// return a copy of the set
func (set *IntSet) Copy() *IntSet {
	return set
}

// 计算 set 中所有元素的和
func (set *IntSet) AddAll() int {
	return 0
}

func main() {
	var x IntSet
	x.Add(1)
	x.Add(144)
	x.Add(9)
	x.String()

	//y.Add(9)
	//y.Add(42)
	//fmt.Println(y.String()) // "{9 42}"
	//
	//x.UnionWith(&y)
	//fmt.Println(x.String()) // "{1 9 42 144}"
	//fmt.Println(x.Has(9), x.Has(123)) // "true false"
}
